#include <new>
//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE 
csArray<T,NeedConstruct,NeedDestruct,alignment>::csArray()
:m_size(0)
,m_capacity(0)
,m_pData(csNULL)
{

}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE 
csArray<T,NeedConstruct,NeedDestruct,alignment>::csArray(const csArray<T,NeedConstruct,NeedDestruct,alignment>& rhs)
:m_size(0)
,m_capacity(0)
,m_pData(csNULL)
{
	_copy(rhs);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment>
csArray<T,NeedConstruct,NeedDestruct,alignment>::csArray(s32 capacity)
:m_size(0)
,m_capacity(capacity)
,m_pData(csNULL)
{
	csASSERT(capacity>=0);
	if(m_capacity>0)
	{
		m_pData = static_cast<T*>(_aligned_malloc(m_capacity*sizeof(T),alignment));
	}
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment>
csArray<T,NeedConstruct,NeedDestruct,alignment>::csArray(s32 size, const T& fileValue)
:m_size(size)
,m_capacity(size)
,m_pData(csNULL)
{
	csASSERT(size>=0);
	if(m_capacity>0)
	{
		m_pData = static_cast<T*>(_aligned_malloc(m_capacity*sizeof(T),alignment));
		for(s32 i=0;i<m_size;i++)
		{
			new(m_pData+i) T(fileValue); 
		}
	}
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment>
csArray<T,NeedConstruct,NeedDestruct,alignment>::csArray(s32 size, const T& fillValue, s32 capacity)
:m_size(size)
,m_capacity(capacity)
,m_pData(csNULL)
{
	csASSERT(capacity>=size);
	csASSERT(size>=0);
	if(m_capacity>=0)
	{
		m_pData = static_cast<T*>(_aligned_malloc(m_capacity*sizeof(T),alignment));
		for(s32 i=0;i<m_size;i++)
		{
			new(m_pData+i) T(fillValue);
		}
	}
}


//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE 
csArray<T,NeedConstruct,NeedDestruct,alignment>::~csArray()
{
	_cleanup();
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE T&
csArray<T,NeedConstruct,NeedDestruct,alignment>::operator[](s32 idx)
{
	csASSERT(idx>=0&&m_size>idx);
	return m_pData[idx];
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE const T&
csArray<T,NeedConstruct,NeedDestruct,alignment>::operator[](s32 idx) const
{
	csASSERT(idx>=0&&m_size>idx);
	return m_pData[idx];
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> void
csArray<T,NeedConstruct,NeedDestruct,alignment>::operator =(const csArray<T,NeedConstruct,NeedDestruct,alignment>& rhs)
{
	if(this!=&rhs)
	{
		//need malloc memory?
		if(0==m_capacity&&rhs.m_size>0)
		{
			m_pData		= static_cast<T*>(_aligned_malloc(rhs.m_size*sizeof(T),alignment));
			m_size		= rhs.m_size;
			m_capacity	= rhs.m_size;
		}

		if(m_capacity>=rhs.m_size)
		{
			s32 i=0;
			for(;i<rhs.m_size;i++)
			{
				m_pData[i] = rhs[i];
			}
			if(NeedDestruct)
			{
				for(;i<m_size;i++)
				{
					m_pData[i].~T();
				}
			}
			m_size = rhs.m_size;
		}
		else
		{
			_cleanup();
			_copy(rhs);
		}
	}
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> bool
csArray<T,NeedConstruct,NeedDestruct,alignment>::operator==(const csArray<T,NeedConstruct,NeedDestruct,alignment>& rhs) const
{
	if(this==&rhs)
	{
		return true;
	}
	if(this->m_size==rhs.m_size)
	{
		for(s32 i=0;i<this->m_size;i++)
		{
			if(!(m_pData[i] == rhs.m_pData[i]))
			{
				return false;
			}
		}
		return true;
	}
	return false;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> bool
csArray<T,NeedConstruct,NeedDestruct,alignment>::operator!=(const csArray<T,NeedConstruct,NeedDestruct,alignment>& rhs) const
{
	return !((*this)==rhs);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE T&
csArray<T,NeedConstruct,NeedDestruct,alignment>::at(s32 idx)
{
	csASSERT(idx>=0&&idx<m_size);
	return m_pData[idx];
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE s32
csArray<T,NeedConstruct,NeedDestruct,alignment>::size() const
{
	return m_size;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::resize(s32 size)
{
	csASSERT(size>=0);
	resize(size,T());
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::resize(s32 size, const T& val)
{
	csASSERT(size>=0);
	if(size>m_capacity)
	{
		_realloc(size);
	}
	if(NeedDestruct)
	{
		for(s32 i=size;i<m_size;i++)
		{
			m_pData[i].~T();
		}
	}
	for(s32 i=m_size;i<size;i++)
	{
		new(m_pData+i) T(val);
	}
	m_size = size;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE s32
csArray<T,NeedConstruct,NeedDestruct,alignment>::capacity() const
{
	return m_capacity;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::_set_capacity(s32 capacity)
{
	csASSERT(capacity>=m_size);
	if(capacity>m_capacity)
	{
		_realloc(capacity);
	}
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE s32
csArray<T,NeedConstruct,NeedDestruct,alignment>::get_reserve() const
{
	return m_capacity - m_size;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::reserve(s32 size)
{
	csASSERT(size>=0);
	_set_capacity(m_size+size);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::swap(csArray<T,NeedConstruct,NeedDestruct,alignment>& rhs)
{
	csSwap<s32>(m_size,rhs.m_size);
	csSwap<s32>(m_capacity,rhs.m_capacity);
	csSwap<T*>(m_pData,rhs.m_pData);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::push_back(const T& rhs)
{
	if(!(m_size<m_capacity))
	{
		_grow();
	}
	new(m_pData+m_size) T(rhs);
	++m_size;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::pop_back()
{
	csASSERT(m_size>0);
	--m_size;
	if(NeedDestruct)
	{
		m_pData[m_size].~T();
	}
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE bool
csArray<T,NeedConstruct,NeedDestruct,alignment>::empty() const
{
	return m_size==0;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> void
csArray<T,NeedConstruct,NeedDestruct,alignment>::clear()
{
	if(NeedDestruct)
	{
		for(s32 i=0;i<m_size;i++)
		{
			m_pData[i].~T();
		}
	}
	m_size = 0;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> void
csArray<T,NeedConstruct,NeedDestruct,alignment>::trim()
{
	T* pData = static_cast<T*>(_aligned_malloc(m_size*sizeof(T),alignment));
	if(NeedConstruct)
	{
		for(s32 i=0;i<m_size;i++)
		{
			new(pData+i) T(m_pData[i]);
		}
	}
	else
	{
		memcpy(pData,m_pData,m_size*sizeof(T));
	}
	if(NeedDestruct)
	{
		for(s32 i=0;i<m_size;i++)
		{
			m_pData[i].~T();
		}
	}
	_aligned_free(m_pData);
	csSwap(pData,m_pData);
	m_capacity = m_size;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> typename csArray<T,NeedConstruct,NeedDestruct,alignment>::iterator
csArray<T,NeedConstruct,NeedDestruct,alignment>::find(const T& val)
{
	for(s32 i=0;i<m_size;i++)
	{
		if(m_pData[i]==val)
		{
			return m_pData+i;
		}
	}
	return m_pData+m_size;
}
//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> typename csArray<T,NeedConstruct,NeedDestruct,alignment>::const_iterator
csArray<T,NeedConstruct,NeedDestruct,alignment>::find(const T& val) const
{
	for(s32 i=0;i<m_size;i++)
	{
		if(m_pData[i]==val)
		{
			return m_pData+i;
		}
	}
	return m_pData+m_size;
}


//preformance fuck
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::insert(s32 idx, const T& ele)
{
	csASSERT(idx>=0&&idx<=m_size);
	if(!(m_size<m_capacity))
	{
		_grow();
	}
	if(idx!=m_size)
	{
		_move(idx,idx+1);
	}
	new(m_pData+idx) T(ele);
	++m_size;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::insert(iterator it, const T &ele)
{
	s32 idx = it - m_pData;
	insert(idx,ele);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> void
csArray<T,NeedConstruct,NeedDestruct,alignment>::insert(s32 idx, const T &ele, s32 num)
{
	csASSERT(num>0&&idx>=0&&idx+num<m_size);
	while(!(m_size+num<=m_capacity))
	{
		_grow();
	}
	if(idx!=m_size)
	{
		_move(idx,idx+num);
	}
	for(s32 i=idx;i<idx+num;i++)
	{
		new(m_pData+i) T(ele);
	}
	m_size+=num;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> void
csArray<T,NeedConstruct,NeedDestruct,alignment>::insert(iterator it, const T& ele, s32 num)
{
	s32 idx = it - m_pData;
	insert(idx,ele,num);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> void
csArray<T,NeedConstruct,NeedDestruct,alignment>::erase(s32 idx, s32 num)
{
	csASSERT(num>0&&idx>=0&&idx+num<=m_size);
	if(NeedDestruct)
	{
		m_pData[idx].~T();
		_move(idx+num,idx);
		for(s32 i=0;i<num;i++)
		{
			m_pData[m_size-1-num].~T();
		}
	}
	else
	{
		_move(idx+num,idx);
	}
	m_size -= num;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::erase(iterator where)
{
	s32 idx = where - m_pData;
	erase(idx);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::erase(iterator beginIt, iterator endIt)
{
	s32 idx = beginIt - m_pData;
	s32 num = endIt - beginIt;
	erase(idx,num);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE typename csArray<T,NeedConstruct,NeedDestruct,alignment>::iterator
csArray<T,NeedConstruct,NeedDestruct,alignment>::begin()
{
	return m_pData;
};

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE typename csArray<T,NeedConstruct,NeedDestruct,alignment>::const_iterator
csArray<T,NeedConstruct,NeedDestruct,alignment>::begin() const
{
	return m_pData;
};

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE typename csArray<T,NeedConstruct,NeedDestruct,alignment>::iterator
csArray<T,NeedConstruct,NeedDestruct,alignment>::end()
{
	return m_pData + m_size;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE typename csArray<T,NeedConstruct,NeedDestruct,alignment>::const_iterator
csArray<T,NeedConstruct,NeedDestruct,alignment>::end() const
{
	return m_pData + m_size;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE T&
csArray<T,NeedConstruct,NeedDestruct,alignment>::front()
{
	csASSERT(m_pData&&0!=m_capacity);
	return *m_pData;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE const T&
csArray<T,NeedConstruct,NeedDestruct,alignment>::front() const
{
	csASSERT(m_pData&&0!=m_capacity);
	return *m_pData;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE T&
csArray<T,NeedConstruct,NeedDestruct,alignment>::back()
{
	csASSERT(m_pData&&0!=m_capacity);
	return m_pData[m_size-1];
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> const csINLINE T&
csArray<T,NeedConstruct,NeedDestruct,alignment>::back() const
{
	csASSERT(m_pData&&0!=m_capacity);
	return m_pData[m_size-1];
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::to_array(T** outArray) const
{
	csASSERT(outArray);
	for(s32 i=0;i<m_size;i++)
	{
		(*outArray)[i] = m_pData[i];
	}
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> void
csArray<T,NeedConstruct,NeedDestruct,alignment>::_copy(const csArray<T,NeedConstruct,NeedDestruct,alignment>& rhs)
{
	csASSERT(0==m_size&&0==m_capacity&&csNULL==m_pData);
	m_size		= rhs.m_size;
	m_capacity	= rhs.m_size;
	if(m_capacity>0)
	{
		m_pData	= static_cast<T*>(_aligned_malloc(m_size*sizeof(T),alignment)); 
		if(NeedConstruct)
		{
			for(s32 i=0;i<m_size;i++)
			{
				new(m_pData+i) T(rhs.m_pData[i]);
			}
		}
		else
		{
			memcpy(m_pData,rhs.m_pData,m_size*sizeof(T));
		}

	}
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::_cleanup()
{
	if(NeedDestruct)
	{
		for(s32 i=0;i<m_size;i++)
		{
			m_pData[i].~T();
		}
	}
	_aligned_free(m_pData);
	m_size		= 0;
	m_capacity	= 0;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> void
csArray<T,NeedConstruct,NeedDestruct,alignment>::_realloc(s32 capacity)
{
	T* pData = static_cast<T*>(_aligned_malloc(capacity*sizeof(T),alignment));
	if(NeedConstruct)
	{
		for(s32 i=0;i<m_size;i++)
		{
			new(pData+i) T(m_pData[i]);
		}
	}
	else
	{
		memcpy(pData,m_pData,m_size*sizeof(T));
	}
	if(NeedDestruct)
	{
		for(s32 i=0;i<m_size;i++)
		{
			m_pData[i].~T();
		}
	}
	_aligned_free(m_pData);
	m_pData		= pData;
	m_capacity	= capacity;
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::_grow()
{
	s32 growStep = m_capacity + 3*m_capacity/8 + 32;
	_realloc(growStep+m_capacity);
}

//------------------------------------------------------------------------
template<typename T,bool NeedConstruct,bool NeedDestruct,s32 alignment> csINLINE void
csArray<T,NeedConstruct,NeedDestruct,alignment>::_move(s32 from, s32 to)
{
	memmove(m_pData+to,m_pData+from,sizeof(T)*(m_size-from));
}